# -*- coding:utf-8 -*-
class Solution:
    # def movingCount(self, threshold, rows, cols):
    #     # write code here
    #     a = [False] * rows * cols
    #     row, col=0,0
    #     lengths = self.help(threshold, rows, cols,row,col,a)
    #     return lengths
    #
    # def help(self,threshold, rows, cols,row,col,a):
    #     m=self.getDigitSum(row)
    #     n=self.getDigitSum(col)
    #     length=0
    #     if 0<=row<rows and 0<=col<cols and m+n<=threshold and a[row * cols + col]==False:
    #         a[row * cols + col] = True
    #         length = 1+self.help(threshold, rows, cols,row-1,col,a) +\
    #         self.help(threshold, rows, cols, row +1, col, a) +\
    #         self.help(threshold, rows, cols, row , col+1, a) +\
    #         self.help(threshold, rows, cols, row , col-1, a)
    #     return length
    #
    # def getDigitSum(self, number):
    #     sum = 0
    #     while number > 0:
    #         sum += (number % 10)
    #         number = number // 10
    #     return sum
    def movingCount(self, threshold, hs, ls):
        # write code here
        a = [False] * hs * ls
        h = l = 0
        lengths = self.help(threshold, hs, ls, h, l, a)
        return lengths

    def help(self, t, hs, ls, h, l, a):
        m = self.helps(h)
        n = self.helps(l)
        length = 0
        if 0 <= h < hs and 0 <= l < ls and m + n <= t and a[h * ls + l] == False:
            a[h * ls + l] = True
            length = 1 + self.help(t, hs, ls, h + 1, l, a) + self.help(t, hs, ls, h - 1, l, a) + self.help(t, hs, ls, h,
                                                                                                           l + 1,
                                                                                                           a) + self.help(
                t, hs, ls, h, l - 1, a)

        return length

    def helps(self, s):
        sums = 0
        while s > 0:
            sums += s % 10
            s = s // 10
        return sums


s = Solution()
print(s.movingCount(2, 3, 2))


